A typical operating system includes a file system. The file system provides a mechanism for the storage and retrieval of files and a hierarchical directory structure for the naming of multiple files. More specifically, the file system stores information provided by the user (i.e., data) and information describing the characteristics of the data (i.e., metadata). The file system also provides extensive programming interfaces to enable the creation and deletion of files, reading and writing of files, performing seeks within a file, creating and deleting directories, managing directory contents, etc. In addition, the file system also provides management interfaces to create and delete file systems. File systems are typically controlled and restricted by operating system parameters. For example, most operating systems limit the maximum number of file names that can be handled within their file system. Some operating systems also limit the size of files that can be managed under a file system.
Once common operation for a file system is to write a file to disk. Initially, when a new file (i.e., a file not previously written to disk) is to be written to disk, the file system must first assign it a file number. Traditional file systems maintain a bitmap for tracking which file numbers have already been allocated (i.e., are in use). Thus, to allocate a file number for the new file, the file system must traverse the bitmap to locate an unused file number. The file system typically traverses the bitmap in O (n) time, where n is the number of allocated file numbers in the bitmap.